package sword.offer;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ThirtyThree {
    /**
     * 注意题中 说道是二叉搜索树。
     * 对于后序遍历来说，数组的最后一个元素是根节点。
     * 由于是二叉搜索树，那么从右往左，第一个比根节点大的数 就是右孩子 遇到第一个比根节点小的数 就是左孩子
     * 这样以此类推 ，就可以证明其是一颗 二叉搜索树
     * */
    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder,0, postorder.length-1);
        }

        boolean recur(int[] postorder, int startIndex, int finishIndex){
            if(finishIndex - startIndex <= 0){
                return true;
            }
            int curRoot = postorder[finishIndex];
            // 找到 左子树的根节点位置
            int index = finishIndex;
            while(index > startIndex){
                if(postorder[--index] < curRoot){
                    break ;
                }
            }
            // 说明当前结点只有一个或者没有左孩子。那么就不需要验证左子树是否合法了。
            if(index == startIndex){
                return recur(postorder, startIndex, finishIndex-1);
            }
            for (int i = startIndex; i < index; i++) {
                if(postorder[i] > curRoot){
                    return false;
                }
            }
            return recur(postorder, startIndex, index) && recur(postorder, index+1, finishIndex-1);
        }
    }

    /**
     * 官方的解答 特别妙！！！
     * 数组的最后一个元素是根节点。
     * 二叉搜索树的性质之一： 左子树 比根节点小  右子树比根节点大 （因为本题不会存在相同的数字）
     * 那么我们根据这个性质 很容易找到 左子树 和 右子树的边界。
     * */
    class Solution1 {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder,0, postorder.length-1);
        }

        boolean recur(int[] postorder, int startIndex, int finishIndex){
            if(startIndex >= finishIndex) return true;
            // 当前的根节点
            int curRoot = postorder[finishIndex];
            int i = startIndex;
            // 这里是左子树的遍历 都比根节点小
            while(postorder[i] < curRoot){i++;}
            int m = i; // 记录右子树的根节点
            // 那么从这里开始 进入到了 右子树的遍历 他们都比根节点大
            while(postorder[i] > curRoot){i++;}

            // 如果i在遍历过程中没有达到根节点的位置 说明左子树中出现了比根节点大的数 或者 右子树出现了比根节点小的数，那么它不是一颗二叉搜索树
            return i == finishIndex && recur(postorder, startIndex, m-1) && recur(postorder, m, finishIndex-1);
        }
    }

}
